package List;

import java.util.PriorityQueue;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-02-28
 * Time:15:44
 * Text：23. 合并 K 个升序链表
 */
public class Text6 {
    /*
    *  暴力解法
    * */
    public ListNode mergeKLists1(ListNode[] lists) {
        ListNode head2=new ListNode(0);
        ListNode cur=head2;
        if(lists.length<=1){
            return head2.next;
        }
        int i=1;
        ListNode head=lists[0];
        while(i<lists.length){
            ListNode t1=head;
            ListNode t2=lists[i];
            while(t1!=null&&t2!=null)
            {
                if(t1.val>=t2.val)
                {
                    cur.next=t2;
                    t2=t2.next;
                }
                else{
                    cur.next=t1;
                    t1=t1.next;
                }
                cur=cur.next;
            }
            if(t1==null)
            {
                cur.next=t2;
            }
            else{
                cur.next=t1;
            }
            head=head2.next;
            i++;
        }
        return head2.next;
    }
    /*
    * 堆方法
    * */
    public ListNode mergeKLists2(ListNode[] lists) {
        //1.创建小根堆
        PriorityQueue<ListNode> heap=new PriorityQueue<>((v1,v2)-> v1.val-v2.val);

        //2.把所有头结点放入小根堆
        for(ListNode head:lists)
            if(head!=null){
                heap.offer(head);
            }
        //3.合并链表
        ListNode ret=new ListNode(0);
        ListNode prev=ret;
        while(!heap.isEmpty()){
            ListNode t1=heap.poll();
            prev.next=t1;
            prev=t1;
            if(t1.next!=null) heap.offer(t1.next);
        }
        return ret.next;
    }
    /*
    * 分治-递归
    * */
    public ListNode mergeKLists3(ListNode[] lists) {
        ListNode head2=new ListNode(0);
        ListNode cur=head2;
        if(lists.length<1){
            return head2.next;
        }
        return sqort(lists,0,lists.length-1);
    }

    public ListNode sqort(ListNode[] lists,int l,int r){
        if(l>=r)return lists[l];
        int mid=(l+r)/2;

        ListNode t1=new ListNode(0);
        ListNode t2=new ListNode(0);

        t1=sqort(lists,l,mid);
        t2=sqort(lists,mid+1,r);

        ListNode head2=new ListNode(0);
        ListNode cur=head2;
        while(t1!=null&&t2!=null)
        {
            if(t1.val>=t2.val)
            {
                cur.next=t2;
                t2=t2.next;
            }
            else{
                cur.next=t1;
                t1=t1.next;
            }
            cur=cur.next;
        }
        if(t1==null)
        {
            cur.next=t2;
        }
        else{
            cur.next=t1;
        }
        return head2.next;
    }

}
